package mylib.dir;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 * Created with IntelliJ IDEA.
 * User: 1
 * Date: 16.07.12
 * Time: 20:00
 * To change this template use File | Settings | File Templates.
 */
public class Graph<T extends Comparable<T>> {
    private Object[] edgeInfo;
    private int[] head, next;
    int edge;

    public Graph() {
        this(0, 0);
    }

    public Graph(int Edges, int Vertexes) {
        edgeInfo = new Object[Edges];
        head = new int[Vertexes];
        next = new int[Edges];
        edge = 0;
        Arrays.fill(head, -1);
    }

    public void addEdge(int u, T w) {
        edgeInfo[edge] = w;
        next[edge] = head[u];
        head[u] = edge++;
    }

    public void sortAdjacentList(int v) {
        ArrayList<T> tmp = adjacentList(v);
        Collections.sort(tmp);
        int index = 0;
        for (int e = head[v]; e >= 0; e = next[e]) {
            edgeInfo[e] = tmp.get(index++);
        }
    }

    public ArrayList<T> adjacentList(int v) {
        ArrayList<T> res = new ArrayList<T>();
        for (int e = head[v]; e >= 0; e = next[e]) {
            res.add((T) edgeInfo[e]);
        }
        return res;
    }
}